class Solution:
    """
    left -> right
    """
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == "0":
            return 0
        
        length = len(s)
        dp = [1] * (length+1)

        for i in range(2, length+1):
            if s[i-1] == "0" and s[i-2] not in ('1', '2'):
                return 0
            elif s[i-2:i] in ('10', '20'):
                dp[i] = dp[i-2]
            elif '10' <= s[i-2:i] <= '26':
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        
        return dp[-1]

if __name__ == '__main__':
    s = Solution()
    print(s.numDecodings("223"))
    